package com.zhugang.week06;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @program algorithms
 * @description: levelOrderLeftRight
 * @author: chanzhugang
 * @create: 2022/07/15 16:39
 */
public class LevelOrderLeftRight {

    /**
     * 剑指offer 32 -III 从上到下打印二叉树 III （之字形打印）
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 第一层从左到右、第二层从右到左
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 两个栈倒腾
        Stack<TreeNode>[] stacks = new Stack[2];
        for (int i = 0; i < 2; i++) {
            stacks[i] = new Stack<>();
        }
        int turn = 0;
        stacks[turn].add(root);

        while (!stacks[turn].isEmpty()) {
            List<Integer> curLevelNodes = new ArrayList<>();

            while (!stacks[turn].isEmpty()) {
                TreeNode treeNode = stacks[turn].pop();
                curLevelNodes.add(treeNode.val);
                if (turn == 0) {
                    // 先左后右
                    if (treeNode.left != null) {
                        stacks[1].push(treeNode.left);
                    }
                    if (treeNode.right != null) {
                        stacks[1].push(treeNode.right);
                    }
                } else {
                    // 先右后左
                    if (treeNode.right != null) {
                        stacks[0].push(treeNode.right);
                    }
                    if (treeNode.left != null) {
                        stacks[0].push(treeNode.left);
                    }
                }
            }
            result.add(curLevelNodes);
            turn = (turn + 1) % 2;
        }
        return result;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}